import javafx.util.Pair;

import java.util.*;

/**
 * 692. 前K个高频单词
 * https://leetcode.cn/problems/top-k-frequent-words/description/
 */
class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //1、预处理以下原始的字符串数组
        Map<String, Integer> hash = new HashMap();
        for(String x : words) {
            hash.put(x, hash.getOrDefault(x, 0) + 1);
        }
        //2、创建一个大小为 k 的堆（频次：小根堆；字典序（频次相同的时候）：大根堆）
        PriorityQueue<Pair<String, Integer>> heap = new PriorityQueue<>(
                (a, b) -> {
                    if(a.getValue().equals(b.getValue())) {
                        //频次相同的时候，字典序按照大根堆的方式排列
                        return b.getKey().compareTo(a.getKey());
                    } else {
                        return a.getValue() - b.getValue();
                    }
                }
        );
        //3、TopK的主逻辑：循环，让元素依次进栈，判断
        for(Map.Entry<String, Integer> e : hash.entrySet()) {
            heap.offer(new Pair<>(e.getKey(), e.getValue()));
            if(heap.size() > k) heap.poll();
        }
        //4、提取结果
        List<String> ret = new ArrayList<>();
        while(!heap.isEmpty()) {
            ret.add(heap.poll().getKey());
        }
        //逆序数组
        Collections.reverse(ret);

        return ret;
    }
}